class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> ret;
        vector<string> path;
        function<void(string&,int)>dfs = [&](string& s,int index)
        {
            if(path.size() == 4)
            {
                if(index == s.length())
                {
                    string ip = path[0]+"."+path[1]+"."+path[2]+"."+path[3];
                    ret.push_back(ip);
                }
                return;
            }//截取完成了
            //从index位置开始截取下一个字符
            for(int i = 1;i<=3;i++)
            {
                if(index+i>s.length())
                {
                    break;
                }//截取当前数目已经超过原字符串大小了，需要剪枝
                string tmp = s.substr(index,i);
                if((tmp.length()>1&&tmp[0] == '0')||stoi(tmp)>255)
                {
                    //存在前导0或者当前截取的字符串大于了255
                    break;
                }
                //当前截取的是一个符合要求的字符串
                path.push_back(tmp);
                dfs(s,index+i);
                path.pop_back();
            }
        };
        dfs(s,0);
        return ret;
    }
};